package 简单.字符串;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出
 * 现次数最多，同时不在禁用列表中的单词。
 * 题目保证至少有一个词不在禁用列表中，而且答案唯一。
 * 禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区
 * 分大小写。答案都是小写字母。
 *  
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/most-common-word
 */
public class 最常见的单词_819 {

    public static void main(String[] args) {

        String[] banned = {"hit"};
        System.out.println(mostCommonWord("a.", banned));

    }

    /**
     * 将禁用单词放入哈希表中
     * 双指针模拟计算非禁用单词出现的次数
     *
     * @param paragraph
     * @param banned
     * @return
     */
    public static String mostCommonWord(String paragraph, String[] banned) {
        // 用一个set来保存禁用列表，查询时间复杂度为O(1)
        Set<String> bannedSet = new HashSet<>();
        Map<String, Integer> map = new HashMap<>();
        for (String ban : banned) {
            bannedSet.add(ban);
        }
        int count = 0;
        String ans = null;
        int left = 0;
        while (left < paragraph.length()) {  // 使用双指针来截取英文单词
            while (left < paragraph.length() && !Character.isLetter(paragraph.charAt(left))) left++;
            if (left == paragraph.length()) break;
            int right = left + 1;
            while (right < paragraph.length() && Character.isLetter(paragraph.charAt(right))) right++;
            String lowerWord = paragraph.substring(left, right).toLowerCase();
            if (!bannedSet.contains(lowerWord)) {
                map.put(lowerWord, map.getOrDefault(lowerWord, 0) + 1);
            }
            left = right;
        }
        for (String word : map.keySet()) {
            if (map.get(word) > count) {
                count = map.get(word);
                ans = word;
            }
        }
        return ans;
    }

}
